package com.leetcode.algorithm.y18.m05;

import java.util.Arrays;

/**
 * leetcode-cn.com
 * 53. 最大子序和
 * 58. 最后一个单词的长度
 * 66. 加一
 * 67. 二进制求和
 * 69. x 的平方根
 * @author dengjie213@126.com 
 * 2018年5月6日 上午10:22:32
 */

public class MySolution0506 {
	/**
	 * 53. 最大子序和 
	 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
	 * 
	 * 示例:
	 * 输入: [-2,1,-3,4,-1,2,1,-5,4], 
	 * 输出: 6 
	 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 
	 * 
	 * 进阶:
	 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
	 * 
	 * @param nums
	 * @return
	 */
	public int maxSubArray(int[] nums) {
		int sum = nums[0];
		int maxSum = sum;
		int length = nums.length;
		for (int i = 1; i < length; i++) {
			if (sum > 0) {
				sum += nums[i];
			}else {
				sum = nums[i];
			}
			if (sum > maxSum) {
				maxSum = sum;
			}
		}
		return maxSum;
	}

	/**
	 * 58. 最后一个单词的长度 
	 * 给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
	 * 
	 * 如果不存在最后一个单词，请返回 0 。
	 * 说明：一个单词是指由字母组成，但不包含任何空格的字符串。
	 * 
	 * 示例:
	 * 输入: "Hello World" 
	 * 输出: 5
	 * 
	 * @param s
	 * @return
	 */
	public int lengthOfLastWord(String s) {
		if ("".equals(s)) {
			return 0;
		}
		// 从后往前，找出第一个字母字符的索引tail[-1 || 0,len-1]，
		// 然后继续往前找到一个空格字符的索引head[-1 || 0,tail)
		// 最后一个单词的长度为tail-head
		char[] chars = s.toCharArray();
		int len = chars.length;
		int tail = len - 1;
		while (tail >= 0 && chars[tail] == ' ') {
			tail--;		
		}
		if (tail < 0) {	//未找到字母字符
			return 0;
		}
		int head = tail;
		while (head >= 0 && chars[head] != ' ') {
			head--;
		}

		return tail - head;
	}

	/**
	 * 66. 加一 
	 * 给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。
	 * 
	 * 最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
	 * 
	 * 你可以假设除了整数 0 之外，这个整数不会以零开头。
	 * 
	 * 示例 1:
	 * 输入: [1,2,3] 
	 * 输出: [1,2,4] 
	 * 解释: 输入数组表示数字 123。 
	 * 
	 * 示例 2:
	 * 输入: [4,3,2,1] 
	 * 输出: [4,3,2,2] 
	 * 解释: 输入数组表示数字 4321。
	 * 
	 * @param digits
	 * @return
	 */
	public int[] plusOne(int[] digits) {
		int len = digits.length;
		if (digits[len - 1] < 9) {
			digits[len - 1] += 1;
			return digits;
		} else {
			if (digits.length == 1) {
				return new int[] { 1, 0 };
			} else {
				int[] digitsPre = plusOne(Arrays.copyOfRange(digits, 0, len - 1));
				return Arrays.copyOf(digitsPre, digitsPre.length + 1);
			}
		}
	}

	/**
	 * 67. 二进制求和 
	 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
	 * 输入为非空字符串且只包含数字 1 和 0。
	 * 
	 * 示例 1:
	 * 输入: a = "11", b = "1" 
	 * 输出: "100" 
	 * 示例 2:
	 * 输入: a = "1010", b = "1011" 
	 * 输出: "10101"
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public String addBinary(String a, String b) {
		//
		// return Integer.toBinaryString(Integer.parseInt(a, 2) +
		// Integer.parseInt(b, 2));
		if ("".endsWith(a)) {
			return b;
		} else if ("".endsWith(b)) {
			return a;
		} else {
			StringBuffer retStr = new StringBuffer();
			int lenA = a.length();
			int lenB = b.length();
			String a1 = addBinary(a.substring(0, lenA - 1), b.substring(0, lenB - 1));
			char charA = a.charAt(lenA - 1);
			char charB = b.charAt(lenB - 1);
			if (charA == '0' && charB == '0') {
				return retStr.append(a1).append("0").toString();
			} else if ((charA == '1' && charB == '0')
					|| (charA == '0' && charB == '1')) {
				return retStr.append(a1).append("1").toString();
			} else {
				return retStr.append(addBinary(a1, "1")).append("0").toString();
			}
		}

	}

	/**
	 * 69. x 的平方根 
	 * 实现 int sqrt(int x) 函数。
	 * 计算并返回 x 的平方根，其中 x 是非负整数。
	 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
	 * 
	 * 示例 1:
	 * 输入: 4 
	 * 输出: 2 
	 * 
	 * 示例 2:
	 * 输入: 8 
	 * 输出: 2 
	 * 
	 * 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
	 * 
	 * @param x
	 * @return
	 */
	public int mySqrt(int x) {
		if (x == 0 || x == 1) {
			return x;
		}
		int begin = 0;
		int end = x;
		int mid = (begin+end/*+1*/)/2;	//【注意】不要加1，避免整数溢出
		
//		long target = x;
		while (end - begin > 1) {
			//int est = mid * mid;		//【注意】mid*mid可能整数溢出，乘法溢出可以用除法
//			long est = Long.valueOf(mid) * Long.valueOf(mid);	
			if (mid == x/mid) {
				return mid;
			}else {
				if (mid > x/mid) {
					end = mid;
				}else {
					begin = mid;
				}
				mid = (begin+end+1)/2; 
			}
		}
		
		return begin;
	}
	
	public int mySqrtBetter(int x) {
		if (x == 0 || x == 1) {
			return x;
		}
		int mid = x / 2;
		int begin = 1;
		int end = x;
		while (end - begin > 1) {
			if (end == x / mid) {
				return mid;
			} else {
				if (mid > x / mid) {
					end = mid;
					begin = x / end;
				} else {
					begin = mid;
					end = x / begin + 1;
				}
				mid = (begin + end + 1) / 2;
			}
		}
		return begin;
	}
	
}